package wh.直接插入排序;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/11/24 16:25
 * @description:直接插入排序
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(null,new ListNode(2,new ListNode(4,new ListNode(3))));
        System.out.println(sortList(listNode));
    }

    public static ListNode sortList(ListNode listNode){
        ListNode pre = listNode,p = listNode.next.next,q;
        //端口首节点与第二个节点 单独一个节点肯定有序
        listNode.next.next = null;
        while (p != null){
            //&&符号左右顺序不能调换，在执行时先左后右
            while (pre.next != null && pre.next.val < p.val){
                pre = pre.next;
            }
            q = p.next;
            p.next = pre.next;
            pre.next = p;
            p = q;
        }
        return listNode;
    }
}
